package com.example.Arithmetic.Arithmetic;

/**
 * 日期：2024/1/2
 * 时间：10:57
 * 描述：快速选择查询
 */
public class QuickSelect {
    static int quick(int[] a, int left, int right, int index) {
        int p = partition(a, left, right);
        if (p == index) {
            return a[p];
        }
        if (p > index) {
            return quick(a, left, p - 1, index);
        } else {
            return quick(a, p + 1, right, index);
        }
    }

    //    j 找比基准点小的，i 找比基准点大的，一旦找到，二者进行交换
    private static int partition(int[] ints, int left, int right) {
        int p = ints[right];
        int j = left;
        int i = left;
        while (j < right) {
//            j小于，所以i不可能更大，执行i++
            if (ints[j] < p) {
                if (i != j) {
                    swap(ints, i, j);
                }
                i++;
            }
            j++;
        }
        swap(ints, i, right);
        return i;
    }

    public static void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    public static void main(String[] args) {
        System.out.println(quick(new int[]{1, 4, 7, 3, 9, 2}, 0, 5, 5));
    }
}
